package com.itheima.algorithm.datastructure;

/**
 * 根据值删除节点
 */
public class Leetcode203 {

    /**
     * 方法1
     *
     * @param head  链表头
     * @param value 目标值
     * @return 删除后的链表头
     */
    public static ListNode removeElements(ListNode head, int value) {

        ListNode s = new ListNode(-1, head);
        ListNode p1 = s;
        ListNode p2 = p1.next;
        while (p2 != null) {
            //找到删除的值
            if (p2.value == value) {
                //删除,p2向后平移
                p1.next = p2.next;
                p2 = p2.next;
            } else {
                //向后平移
                p1 = p1.next;
                p2 = p2.next;
            }
        }
        return s.next;
    }

    /**
     * 思路: 递归函数负责返回,从当前节点开始,完成删除的链表
     * 1. 若我与v相等,应返回下一个节点递归结果
     * 2. 若我与v不相等,应该返回我,但我的next应该更新,(让我能带上后续删过的节点
     * )
     *
     * @param p   链表头
     * @param val 目标值
     * @return 删除后的链表头
     */
    public static ListNode removeElementsByRecursion(ListNode p, int val) {
        if (p == null) {
            return null;
        }
        if (p.value == val) {
            //相等,返回下一个节点的递归结果
            return removeElementsByRecursion(p.next, val);
        } else {
            p.next = removeElementsByRecursion(p.next, val);
            return p;
        }
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2, 6, 3, 6);
        System.out.println(head);

        ListNode result = removeElementsByRecursion(head, 6);
        System.out.println(result);
    }
}
